package arithmetic.demo20;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 动态规划： 含义dp + 分类讨论 + 特殊点标记 ：01背包
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt(), maxV = in.nextInt();
        // 用一个背包表示， 第一个表示体积，第二个位置表示重
        int[][] bag = new int[len][2];

        // 输入
        for (int i = 0 ; i < len; i++) {
            // 输入体积 和 重量
            bag[i][0] = in.nextInt();
            bag[i][1] = in.nextInt();
        }

        // 创建 dp
        int[][] dp = new int[maxV + 1][len + 1];

        for (int i = 1; i <= maxV; i++) {
            for (int j = 1; j <= len; j++) {
                // 继承当下体积的上一个物块的重量
                dp[i][j] = dp[i][j - 1];

                // 如果还能装下就继续装
                if ( i - bag[j - 1][0] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - bag[j - 1][0]][j - 1] + bag[j - 1][1]);
                }
            }
        }

        // 这里重新创建 gp
        int[][] gp = new int[maxV+1][len+1];



        // 初始化
        for(int j = 1 ; j <= maxV; j++) {
            // 没有物品但是有体积， 说明为 -1
            gp[j][0] = -1;
        }
        // 从上往下填表
        for (int i = 1; i <= maxV; i++) {
            for (int j = 1; j <= len; j++) {
                int index = i - bag[j-1][0];
//                先继承v刚好等于 i 并且是前一个位置的数据
                gp[i][j] = gp[i][j-1];
                if(index >= 0 && gp[index][j - 1] != -1) {
                    gp[i][j] = Math.max( gp[index][j - 1]  + bag[j-1][1], gp[i][j]);
                }
            }
        }

        System.out.println(  dp[maxV][len]);
        int ret =  gp[maxV][len] == -1 ? 0 : gp[maxV][len];
        System.out.println( ret);
    }
}


/**
 * 动态规划： 含义dp + 分类讨论 + 特殊点标记 ：01背包（空间优化版本）
 */


// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt(), maxV = in.nextInt();
        // 用一个背包表示， 第一个表示体积，第二个位置表示重
        int[][] bag = new int[len][2];

        // 输入
        for (int i = 0 ; i < len; i++) {
            // 输入体积 和 重量
            bag[i][0] = in.nextInt();
            bag[i][1] = in.nextInt();
        }

        // 创建 dp
        int[] dp = new int[maxV + 1];

        // 实现滚动数组来优化
        for (int i = 1 ; i <= len; i++) {
            for (int j = maxV; j >= 0; j--) {
                // 获取剩余体积
                int indexV = j - bag[i-1][0];
                if (indexV >= 0) {
                    // 取原先的
                    // 和加上之后的最大重量
                    dp[j] = Math.max(dp[j], dp[indexV] + bag[i-1][1]);
                }
            }
        }

        // 输入不大于最大体积的背包重量
        System.out.println(dp[maxV]);

        // 这里重新初始化 gp
        Arrays.fill(dp, 0);


        // 初始化
        for (int j = 1 ; j <= maxV; j++) {
            // 体积 == 0但是有物品可以添加， 说明装不下了， 就初始化为 -1
            dp[j] = -1;
        }
        // 从上往下填表
        // 实现滚动数组来优化
        for (int i = 1 ; i <= len; i++) {
            for (int j = maxV; j >= 0; j--) {
                // 获取剩余体积
                int indexV = j - bag[i-1][0];
                if (indexV >= 0 && dp[indexV] != -1) {
                    // 取原先的
                    // 和加上之后的最大重量
                    dp[j] = Math.max(dp[j], dp[indexV] + bag[i-1][1]);
                }
            }
        }

        // 输出 等于最大体积的重量
        System.out.println( dp[maxV] == -1 ? 0 : dp[maxV]);
    }
}



/**
 * 动态规划： 含义dp + 分类讨论 + 特殊点标记 ：01背包（空间优化版本2）
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt(), maxV = in.nextInt();
        // 用一个背包表示， 第一个表示体积，第二个位置表示重
        int[][] bag = new int[len][2];

        // 输入
        for (int i = 0 ; i < len; i++) {
            // 输入体积 和 重量
            bag[i][0] = in.nextInt();
            bag[i][1] = in.nextInt();
        }

        // 创建 dp
        int[] dp = new int[maxV + 1];

        // 实现滚动数组来优化
        for (int i = 1 ; i <= len; i++) {
            // 直接让 体积大于 背包体积即可
            for (int j = maxV;  j >= bag[i-1][0]; j--) {
                // 获取剩余体积
                // 取原先的
                // 和加上之后的最大重量
                dp[j] = Math.max(dp[j], dp[j - bag[i-1][0]] + bag[i-1][1]);

            }
        }

        // 输入不大于最大体积的背包重量
        System.out.println(dp[maxV]);

        // 这里重新初始化 gp
        Arrays.fill(dp, 0);


        // 初始化
        for (int j = 1 ; j <= maxV; j++) {
            // 体积 == 0但是有物品可以添加， 说明装不下了， 就初始化为 -1
            dp[j] = -1;
        }
        // 从上往下填表
        // 实现滚动数组来优化
        for (int i = 1 ; i <= len; i++) {
            for (int j = maxV; j >= bag[i-1][0]; j--) {
                // 获取剩余体积
                int  index =  j - bag[i-1][0];
                if (dp[index] != -1) {
                    // 取原先的
                    // 和加上之后的最大重量
                    dp[j] = Math.max(dp[j], dp[index] + bag[i-1][1]);
                }
            }
        }

        // 输出 等于最大体积的重量
        System.out.println( dp[maxV] == -1 ? 0 : dp[maxV]);
    }
}



